#include "BigInteger.h"

#include <cmath>
#include <sstream>

namespace
  {
  std::string LongToString(long long int i_a)
    {
    std::ostringstream ss;
    ss << i_a;
    return ss.str();
    }

  int Sign(int i_val)
    {
    return (i_val > 0) - (i_val < 0);
    }
  }

BigInteger::BigInteger() : m_base(10000)
  {
  m_data.assign(1, 0);
  }

BigInteger::BigInteger(const BigInteger& other) : m_base(10000), m_data(other.m_data)
  {
  }

BigInteger::BigInteger(BigInteger&& other) : m_base(10000), m_data(std::move(other.m_data))
  {
  }

BigInteger::BigInteger(long long int i_init) : m_base(10000)
  {
  this->m_data = BigInteger(LongToString(i_init)).m_data;
  }

BigInteger::BigInteger(const std::string& i_init) : m_base(10000)
  {
  if (i_init.size() == 0)
    {
    m_data.assign(1, 0);
    return;
    }

  int start_pos = 0;
  if (i_init[0] == '-')
    {
    ++start_pos;
    }

  for (int i = static_cast<int>(i_init.size()) - 1; i >= start_pos; i -= 4)
    {
    int cur_digit = 0;
    for (int j = std::max(start_pos, i - 3); j <= i; ++j)
      {
      if (i_init[j] < '0' || i_init[j] > '9')
        {
        throw std::string("Can't construct form string");
        }
      cur_digit = 10 * cur_digit + static_cast<int>(i_init[j] - '0');
      }
    if (start_pos == 1)
      {
      cur_digit *= -1;
      }
    m_data.push_back(cur_digit);
    }
  }

BigInteger::~BigInteger()
  {
  }


BigInteger::operator std::string()
  {
  std::string string_value = "";
  int sign = m_data.back() < 0 ? -1 : 1;
  for (int i = static_cast<int>(m_data.size()) - 1; i >= 0; --i)
    {
    char buffer[5] = {0};
    if (i + 1 == m_data.size())
      {
      sprintf_s(buffer, "%d", sign * m_data[i]);
      }
    else
      {
      sprintf_s(buffer, "%04d", sign * m_data[i]);
      }
    string_value += buffer;
    }
  if (sign == -1)
    {
    string_value = "-" + string_value;
    }
  return string_value;
  }

BigInteger& BigInteger::operator = (const BigInteger& other)
  {
  m_data = other.m_data;
  return *this;
  }

BigInteger& BigInteger::operator ++ ()
  {
  *this += BigInteger(1);
  return *this;
  }

BigInteger BigInteger::operator ++ (int)
  {
  BigInteger ret = *this;
  *this += BigInteger(1);
  return ret;
  }

BigInteger& BigInteger::operator -- ()
  {
  *this -= BigInteger(1);
  return *this;
  }

BigInteger BigInteger::operator -- (int)
  {
  BigInteger ret = *this;
  *this -= BigInteger(1);
  return ret;
  }

BigInteger BigInteger::operator + () const
  {
  return *this;
  }

BigInteger BigInteger::operator - () const
  {
  BigInteger ret(*this);
  for (size_t i = 0; i < ret.m_data.size(); ++i)
    {
      ret.m_data[i] *= -1;
    }
  return ret;
  }

BigInteger BigInteger::operator + (const BigInteger& other) const
  {
  BigInteger ret(*this);
  ret += other;
  return ret;
  }

BigInteger BigInteger::operator - (const BigInteger& other) const
  {
  return -(-*this + other);
  }

BigInteger BigInteger::operator * (const BigInteger& other) const
  {
  BigInteger ret;
  ret.m_data.assign(m_data.size() + other.m_data.size() - 1, 0);
  for (size_t i = 0; i < m_data.size(); ++i)
    {
    for (size_t j = 0; j < other.m_data.size(); ++j)
      {
      ret.m_data[i + j] += m_data[i] * other.m_data[j];
      if (abs(ret.m_data[i + j]) >= m_base)
        {
        int delta = ret.m_data[i + j] / m_base;
        ret.m_data[i + j] %= m_base;
        if (i + j + 1 == ret.m_data.size())
          {
          ret.m_data.push_back(0);
          }
        ret.m_data[i + j + 1] += delta;
        }
      }
    }
  for (size_t i = 0; i < ret.m_data.size(); ++i)
    {
    if (abs(ret.m_data[i]) >= m_base)
      {
      int delta = ret.m_data[i] / m_base;
      ret.m_data[i] %= m_base;
      if (i + 1 == ret.m_data.size())
        {
        ret.m_data.push_back(0);
        }
      ret.m_data[i + 1] += delta;
      }
    }
  while (ret.m_data.back() == 0 && ret.m_data.size() > 1)
    {
    ret.m_data.pop_back();
    }
  return ret;
  }

BigInteger BigInteger::operator / (const BigInteger& other) const
  {
  BigInteger ret(*this);
  ret /= other;
  return ret;
  }

BigInteger BigInteger::operator % (const BigInteger& other) const
  {
  BigInteger ret(*this);
  ret %= other;
  return ret;
  }

BigInteger& BigInteger::operator += (const BigInteger& other)
  {
  if (m_data.size() < other.m_data.size())
    {
    m_data.resize(other.m_data.size(), 0);
    }
  for (size_t i = 0; i < other.m_data.size(); ++i)
    {
    m_data[i] += other.m_data[i];
    }
  for (size_t i = 0; i < m_data.size(); ++i)
    {
    if (abs(m_data[i]) >= m_base)
      {
      int delta = m_data[i] / m_base;
      m_data[i] %= m_base;
      if (i + 1 == m_data.size())
        {
        m_data.push_back(0);
        }
      m_data[i + 1] += delta;
      }
    if (m_data[i] < 0 && i + 1 != m_data.size())
      {
      m_data[i] += m_base;
      --m_data[i + 1];
      }
    }
  if (m_data.back() < 0)
    {
      for (size_t i = 0; i + 1 < m_data.size(); ++i)
        {
        m_data[i] -= m_base;
        ++m_data[i + 1];
        }
    }
  while (m_data.back() == 0 && m_data.size() > 1)
    {
    m_data.pop_back();
    }
  return *this;
  }

BigInteger& BigInteger::operator -= (const BigInteger& other)
  {
  this->m_data = (*this - other).m_data;
  return *this;
  }

BigInteger& BigInteger::operator *= (const BigInteger& other)
  {
  this->m_data = (*this * other).m_data;
  return *this;
  }

BigInteger& BigInteger::operator /= (const BigInteger& other)
  {
  if (other == BigInteger(0))
    {
    throw std::string("Division by zero");
    }
  int res_sgn = 1;
  if (*this < BigInteger(0)) res_sgn *= -1;
  if (other < BigInteger(0)) res_sgn *= -1;
  if (*this < BigInteger(0))
    {
    *this = -(*this);
    }
  std::vector<BigInteger> power_2(1, BigInteger(1)), power_other_2(1, other > BigInteger() ? other : -other);
  while (power_other_2.back() < *this)
    {
    power_other_2.push_back(power_other_2.back() * BigInteger(2));
    power_2.push_back(power_2.back() * BigInteger(2));
    }
  BigInteger res, left = *this;
  for (int i = power_2.size() - 1; i >= 0; --i)
    {
    if (left >= power_other_2[i])
      {
      left -= power_other_2[i];
      res += power_2[i];
      }
    }
  this->m_data = res.m_data;
  if (res_sgn == -1) *this = -(*this);
  return *this;
  }

BigInteger& BigInteger::operator %= (const BigInteger& other)
  {
  if (other == BigInteger(0))
    {
    throw std::string("Division by zero");
    }
  int res_sgn = 1, init_less = 0;
  if (*this < BigInteger(0))
    {
    res_sgn *= -1;
    init_less = 1;
    }
  if (other < BigInteger(0)) res_sgn *= -1;
  if (*this < BigInteger(0))
    {
    *this = -(*this);
    }
  std::vector<BigInteger> power_2(1, BigInteger(1)), power_other_2(1, other > BigInteger() ? other : -other);
  while (power_other_2.back() < *this)
    {
    power_other_2.push_back(power_other_2.back() * BigInteger(2));
    power_2.push_back(power_2.back() * BigInteger(2));
    }
  BigInteger res, left = *this;
  for (int i = power_2.size() - 1; i >= 0; --i)
    {
    if (left >= power_other_2[i])
      {
      left -= power_other_2[i];
      res += power_2[i];
      }
    }
  if (init_less) left = -left;
  this->m_data = left.m_data;
  return *this;
  }

bool BigInteger::operator < (const BigInteger& other) const
  {
  if (Sign(m_data.back()) != Sign(other.m_data.back()))
    {
    return Sign(m_data.back()) < Sign(other.m_data.back());
    }
  bool sgn_ret = true;
  if (Sign(m_data.back()) == -1)
    {
    sgn_ret = false;
    }
  if (m_data.size() < other.m_data.size())
    {
    return sgn_ret;
    }
  if (m_data.size() > other.m_data.size())
    {
    return !sgn_ret;
    }
  for (int i = m_data.size() - 1; i >= 0; --i)
    {
    if (m_data[i] < other.m_data[i])
      {
      return true;
      }
    if (m_data[i] > other.m_data[i])
      {
      return false;
      }
    }
  return false;
  }

bool BigInteger::operator <= (const BigInteger& other) const
  {
  return *this < other || *this == other;
  }

bool BigInteger::operator > (const BigInteger& other) const
  {
  return other < *this;
  }

bool BigInteger::operator >= (const BigInteger& other) const
  {
  return *this > other || *this == other;
  }

bool BigInteger::operator == (const BigInteger& other) const
  {
  return !(*this > other || *this < other);
  }

bool BigInteger::operator != (const BigInteger& other) const
  {
  return *this > other || *this < other;
  }